package tree;
public class RedBlackTree {
	private TreeNode header;	//指向根节点
	private TreeNode current;	//指向当前节点
	private TreeNode parent;	//父节点
	private TreeNode grand;		//祖父节点
	private TreeNode great;		//曾祖父
	
	public enum Color {
		RED, BLACK
	}
	
	public RedBlackTree(TreeNode header) {
		this.header = header;
	}

	//插入一个节点
	public void insert(int x){
		current = parent = grand = header;
		
		while(current != null && current.val != x) {
			great = grand; grand = parent; parent = current;
			current = x < current.val ? current.left : current.right;
			if(current != null && current.right != null && current.left != null && current.left.color == Color.RED && current.right.color == Color.RED) {
				handleReorient(x);
			}
		}
		if(current != null) {
			System.out.println("插入失败");
		}else {
			current = new TreeNode(x);
			if(x < parent.val) {
				parent.left = current;
			}else {
				parent.right = current;
			}
		}
		//System.out.println(current.val);
		//自动平衡 ---新插入节点红色的，父节点也是红色的就需要再平衡
		handleReorient(x);
	}
	
	//平衡红黑树
	private void handleReorient(int x) {
		//变色
		current.color = Color.RED;
		if(current.left != null) {
			current.left.color = Color.BLACK;
		}
		if(current.right != null) {
			current.right.color = Color.BLACK;
		}
		
		if(parent.color == Color.RED) {
			grand.color = Color.RED;
			if(x < grand.val != x < parent.val) {
				parent = rotate(x, grand);
			}
			current = rotate(x, great);
			current.color = Color.BLACK;
		}
		header.right.color = Color.BLACK;
	}
	public TreeNode rotate(int x, TreeNode xParent) {
		if(x < xParent.val) {
			if(x < xParent.left.val){
				rotateWithLeftChild(xParent.left); 
			}else {
				rotateWithRightChild(xParent.left);
			}
			return xParent.left;
		}else {
			if(x < xParent.right.val) {
				rotateWithLeftChild(xParent.right);
			}else {
				rotateWithRightChild(xParent.right);
			}
			return xParent.right;
		}
	}
	//旋转
	public void rotateWithLeftChild(TreeNode k2) {
		TreeNode k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		k2 = k1;
	}
	public void rotateWithRightChild(TreeNode k1) {
		TreeNode k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		k1 = k2;
	}
	//**************************************************
	//********双旋转
	public void doubleRotateWithLeftChild(TreeNode k3) {
		rotateWithRightChild(k3.left);
		rotateWithLeftChild(k3);
	}
	public void doubleRotateWithRightChild(TreeNode k1) {
		rotateWithLeftChild(k1.right);
		rotateWithRightChild(k1);
	}
}
